/*
    dp[i][j]表示i~j的最长回文子序列的长度
        a. 如果一个子序列是一个回文子序列，那么去掉头尾两个字符后也还是回文子序列
        b. 如果s[i] == s[j]
            1. 如果i，j是相邻的两字符，那dp[i][j] = 2;
            2. 否则，dp[i][j] = 2 + dp[i + 1][j - 1]
        c. 否则dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
*/
//dp[i][j]表示 i~j的最长回文自序列的长度
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        vector<vector<short>>dp (n, vector<short>(n, 1));

        for (int j = 0; j < n; j++)
        {
            for (int i = j - 1; i >= 0; i--)
            {
                if (s[j] == s[i])
                {
                    if (j - i == 1)
                        dp[i][j] = 2;
                    else
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                }
                else
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }

        return dp[0][n - 1];
    }
};